#ifndef WD_SORT_H
#define WD_SORT_H

typedef int ElemType;

void InsertSort(ElemType A[], int n)
{
    int i, j;
    for (i = 2; i <= n; i++)
        if (A[i] < A[i - 1])
        {
            A[0] = A[i];
            for (j = i - 1; A[0] < A[j]; --j)
                A[j + 1] = A[j];
            A[j + 1] = A[0];
        }
}
void BinaryInsertSort(ElemType A[], int n)
{
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++)
    {
        A[0] = A[i];
        low = 1;
        high = i - 1;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (A[mid] > A[0])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j];
        A[high + 1] = A[0];
    }
}
#endif /* WD_SORT_H */